(Not Applicable)
(Not Applicable)
1. Technical Field
This invention relates to the field of natural language understanding, and more particularly, to a method for identifying members of classes in a conversational natural language understanding system.
2. Description of the Related Art
Natural language understanding (NLU) systems enable computers to understand and extract information from human written or spoken language. Such systems can function in a complimentary manner with a variety of other computer applications where there exists a need to understand human language. NLU systems can extract relevant information contained within text and then supply this information to another application program or system for purposes such as booking flight reservations, finding documents, or summarizing text.
Currently within the art, many NLU systems are implemented as directed dialog systems. Directed dialog NLU systems typically prompt or instruct a user as to the proper form of an immediate user response. For example, a directed dialog NLU system can instruct a user as follows xe2x80x9cSay 1 for choice A, Say 2 for choice Bxe2x80x9d. By instructing the user as to the proper format for an immediate user response, the NLU system can expect a particular formatted speech response as input.
In contrast to a directed dialog NLU system, a conversational NLU system does not give a user directed and immediate guidance as to the proper form and content of a user response. Rather than guiding a user through a series of menus, such systems allow a user to issue practically any command or request for information at any time. Accordingly, a conversational NLU system must be able to understand and process those user responses at any point within a given dialog.
Within a conversational NLU system, a component called a classer can be used to identify text words belonging to a particular class of words. Common examples of word classes can include, but are not limited to, dates, times, mutual funds, or airlines. For example, a travel reservation system would be required to understand user requests for airline information or particular user specified airlines. Thus, the NLU system can be designed to identify airline names within a received text input wherein each airline name can be a member of a class called AIRLINE. Similarly, a financial management application can manage financial accounts wherein any specific mutual fund recognizable by the system can be a member of a class called FUND. Some classes, such as times or dates, can be application independent. Such classes can be represented relatively easily using context free grammars.
Generally, a grammar is a formal specification of the structures allowable in a language where the rules can be denoted using Backus-Naur Form (BNF). For example, a sentence can be denoted as xe2x80x9cS :=NP VPxe2x80x9d, where the well formed sentence xe2x80x9cSxe2x80x9d can consist of a noun phrase (NP) and a verb phrase (VP). Notably, phrases and groups of phrases can be referred to as non-terminals. Accordingly, xe2x80x9cNPxe2x80x9d and xe2x80x9cVPxe2x80x9d can be referred to as non-terminals. Also, each element of the rule further can be parsed to the terminal or word level. For example, xe2x80x9cNP :=ART Nxe2x80x9d can be a parse of a noun phrase having an article (ART) and a noun (N), such as xe2x80x9ca boyxe2x80x9d. A grammar comprised of a system of rules having a single symbol on the left-hand side is said to be a context-free grammar.
Other classes, for example FUND or AIRLINE, tend to be application dependent. Application dependent classes can be represented using lists of allowable phrases or grammars designed to accept substrings of the full list.
Users of conversational NLU systems often do not fully and completely specify the arguments upon which a specified request or command can operate. For example, if a user requests information pertaining to a particular mutual fund within the user""s portfolio, the user may say xe2x80x9ctell me the performance of XYZ Fundxe2x80x9d, wherein xe2x80x9cXYZ Fundxe2x80x9d is the argument of the user specified action. The actual fund name, however, may be the xe2x80x9cXYZ Aggressive Small Cap Growth Fundxe2x80x9d. In that case, the lists of allowable phrases or grammars, for example a class, must contain an entry or member for xe2x80x9cXYZ Fundxe2x80x9d which informs the NLU system that the phrase unambiguously refers to the correct fund name xe2x80x9cXYZ Aggressive Small Cap Growth Fundxe2x80x9d. Still, if the NLU system must distinguish between a variety of funds from the XYZ company, the phrase xe2x80x9cXYZ Fundxe2x80x9d is not informative. For example, XYZ company can offer 30 different funds, each having the terms xe2x80x9cXYZxe2x80x9d and xe2x80x9cFundxe2x80x9d within the fund name. As a result, lists or grammars which are capable of accepting substrings of full strings, oftentimes can yield an ambiguous result, wherein multiple possible matches can exist for a particular argument. Notably, in this example, xe2x80x9cXYZ Fundxe2x80x9d can correspond to some thirty possible members of the FUND class. Such lists or grammars are said to be ambiguous.
Grammatical ambiguities, however, must be resolved in a conversational NLU system. For example, the NLU system must recognize that the user specified argument xe2x80x9cXYZ Fundxe2x80x9d can relate to over 30 possible funds. Accordingly, the NLU system must query the user for additional information to resolve which XYZ fund was intended by the user. One disadvantage of using an ambiguous list or grammar can be that the first possible match within the list or grammar is typically returned as a possible match for the user specified argument of the text input. Thus, an ambiguous list or grammar can fail to return an exhaustive listing of members of a class which can be possible matches for the user specified argument. Moreover, typically there is no way of ensuring that the returned member is the most accurate match within the list or grammar.
One proposed solution has been to use search engines to determine the user intended argument. Still, the use of search engines can be problematic. Typically, a search engine can locate some possible arguments, but search engines tend to find the shortest possible matches for the received user input and can overlook longer possible matches. Another disadvantage of conventional solutions can be the ease with which bugs can be introduced into the system when new members are added to a class. For example, the addition of members to a class can require many new xe2x80x9crulesxe2x80x9d to be added to the system. The interoperability of the new rules with the old rules can be difficult to analyze. In particular, the introduction of new rules can introduce ambiguities into the NLU system. Additionally, because the new rules impact the existing rules and often require the existing rules to be updated or edited, the likelihood of introducing bugs into the NLU system increases as additional members are included within a class. This can make NLU systems difficult, not only to maintain, but also to update.
The invention disclosed herein concerns a method for identifying members of classes in a natural language understanding (NLU) system. Generally, the invention enables additional members to be added to a class with little or no concern over retraining a statistical model or introducing conflicts or ambiguities into grammar based rules. User utterances converted to text or other text inputs containing possible members belonging to a particular class can be identified though the member may have been inaccurately or incompletely specified. The method can be particularly useful with regard to conversational NLU systems where ambiguities must be resolved. A word spotting algorithm in combination with a lookup table type of data structure can be used to resolve ambiguities and also to simplify updating and maintenance of a class of members. Accordingly, fewer errors can be introduced into the NLU system because existing rules need not be constantly rewritten to accommodate new members. Rather, the NLU system can search for substrings of an identified possible member and determine a likely member match based upon an intersection or union of matched substrings.
In particular, the invention provides a method of resolving ambiguities within a grammar or list of acceptable phrases in an NLU system. The invention can be configured by assigning a unique value to members of a class in the NLU system. A list of possible substrings, referred to a substring entries, can be determined from the members of the class and included within a data structure. Each substring entry can be associated with the value corresponding to each member having at least one term in common with the substring entry. In operation, received text string inputs can be processed by an NLU system classer. The classer, either grammatically based or statistically based, can identify text strings which can be possible members, but have been inaccurately or incompletely specified. The NLU system can search the substring entries for variations of an identified possible user specified member. For each match, the NLU system can store one or more values. Subsequently, the NLU system can take an intersection or union of the values to determine one or more member matches. Notably, the method can be performed using a word spotting algorithm and a lookup table type of data structure.
One aspect of the invention can be a method of configuring classes in an NLU system including a series of steps. The steps can include assigning a unique value to members of a class in an NLU system and generating possible substrings from the members of the class. For each generated substring having at least one term in common with one of the members in the class, the step of associating with the generated substring the unique value assigned to the member can be included.
Another aspect of the invention can be a method of identifying members of classes in an NLU system. In that case, the method can include the step of (a) receiving a text string input and identifying a possible member of an NLU class within the text string input. The step of (b) matching a longest possible term substring of the possible member to a substring entry in a list of substrings generated from actual members within an NLU class can be included. Notably, each actual member can have a corresponding unique value. Additionally, step (b) can begin with a first term of the possible member. If a match is found in step (b), the step of (c) associating one or more values corresponding to the substring entry with the possible member wherein each value can correspond to one of the actual members of the class can be included. The additional step of repeating steps (b) and (c) for a next term in the possible member until no terms remain in the possible member can be included.
If a match is found in step (b), beginning with a term in the possible member to the right of a rightmost term of the matched substring of the possible member, the additional step of matching a longest possible substring of the possible member to a substring entry from the list can be included. If no match is found in step (b), beginning with a next term to the right in the possible member, the step of matching a longest possible substring of the possible member to a substring entry in the list can be included.
Another embodiment of the invention can include the additional steps of taking an intersection or a union of the values associated with the possible member and selecting at least one actual member corresponding to the intersection or union of the values. Also, the step of querying a user for additional information to resolve an ambiguity in the intersection or union of the values can be included.
Another aspect of the invention can be a machine readable storage, having stored thereon a computer program having a plurality of code sections executable by a machine for causing the machine to perform a series of steps for configuring classes in an NLU system. The steps can include assigning a unique value to members of a class in an NLU system and generating possible substrings from the members of the class. For each generated substring having at least one term in common with one of the members in the class, the step of associating with the generated substring the unique value assigned to the member can be included.
Another aspect of the invention can be a machine readable storage, having stored thereon a computer program having a plurality of code sections executable by a machine for causing the machine to perform a series of steps for identifying members of classes in an NLU system. In that case, the step of (a) receiving a text string input and identifying a possible member of an NLU class within the text string input can be included. The step of (b) matching a longest possible term substring of the possible member to a substring entry in a list of substrings generated from actual members within an NLU class can be included. Notably, each actual member can have a corresponding unique value. Additionally, step (b) can begin with a first term of the possible member. If a match is found in step (b), the step of (c) associating one or more values corresponding to the substring entry with the possible member wherein each value can correspond to one of the actual members of the class can be included. The additional step of repeating steps (b) and (c) for a next term in the possible member until no terms remain in the possible member can be included.
If a match is found in step (b), beginning with a term in the possible member to the right of a rightmost term of the matched substring of the possible member, the additional step of matching a longest possible substring of the possible member to a substring entry from the list can be included. If no match is found in step (b), beginning with a next term to the right in the possible member, the step of matching a longest possible substring of the possible member to a substring entry in the list can be included.
Another embodiment of the invention can include additional code sections for causing the machine to perform the steps of taking an intersection or a union of the values associated with the possible member and selecting at least one actual member corresponding to the intersection or union of the values. Also, the step of querying a user for additional information to resolve an ambiguity in the intersection or union of the values can be included.